googologywikiaorg-20200223-history
User blog:Vel!/Hilbert ITTMs
Within hours of setting up our IRC channel ##googology, an interesting discussion occurred (edited for privacy and brevity): 12:32:55 Anyways, let's talk math 12:33:15 some dude is raving about "infinity-dimensional Turing machine" http://googology.wikia.com/wiki/User:65.26.80.144 12:33:32 I didn't even waste my time reading that 12:33:46 However it is actually an interesting idea if we put a TM in Hilbert space 12:33:55 Why not, that's fun 12:33:56 and use ITTM instead of TM 12:33:57 It is 12:34:18 However we would need to revise the rules a bit 12:34:26 But how would ruleset work 12:34:41 We would have infinitely many ways to move 12:34:46 How to choose one? 12:35:19 We need a way to specify an arbitrary natural number, and have the TM move in that direction 12:35:46 the important thing is that this number must be specified at runtime 12:36:08 I don't really see how this is supposed to work 12:36:20 You could do something very, very clunky 12:36:59 In addition to L and R, the motion M reads the 1D tape along (x, 0, 0, ...) 12:37:21 and adds that vector to the TM's current position 12:37:55 it's a start, although it basically leaves the TM stranded after moving outside of the line :/ 12:38:16 Hilbert space is uncountable, right? 12:38:26 I didn't use the right term 12:38:54 it's a countably infinite set of natural-number coordinate positions 12:39:08 equivalent to Bowers' X^X space 12:39:08 Okay 12:39:15 I see 12:39:42 So only finitely many coordinates can be nonzero 12:39:45 At a time 12:39:51 Right. 12:40:07 But if we use ITTM instead of TM... 12:42:33 ...then we have no control over how many coordinates are finite 12:42:53 *are nonzero 12:43:09 How come? 12:43:30 Well, using your idea of adding vectors 12:43:42 Machine can write infinitely many ones 12:43:45 And boom 12:44:33 what are the consequences of that? 12:44:56 Then we are working in uncountable Hilbert space 12:45:13 Sure. 12:45:26 Okay, so it's not a problem 12:45:33 However it seems we can only access countably many positions in the Hilbert space 12:45:54 because there are countably many rules that can lead up to the M motion 12:46:48 In other words, at all points the machine's position vector must be somehow computable with ITTMs, I believe :( ... 13:10:05 Regarding Hilbert ITTMs 13:10:27 although exploring higher-order spaces is interesting, I hypothesize that it ultimately gets us nowhere 13:10:46 Hilbert ITTMs? 13:10:47 Yeah 13:11:05 The idea is this 13:11:27 We have an ITTM with one tape head and other head inside a Hilbert space 13:11:52 We now use the tape to specify where we move Hilbert space head 13:12:11 I think it's clear where this is going 13:12:22 so the colors in the 1D tape encode a vector that gets added to the Hilbert head's position 13:13:23 it's important that the machine is infinite-time, so we can access positions with infinitely many nonzero coordinates 13:13:37 so we are talking about Z^Z rather than a Hilbert space really 13:13:45 yeah, I didn't quite know what to call it 13:13:48 Actually, yeah 13:13:58 or 2^Z 13:14:02 It's a discrete subset of Hilbert space 13:14:48 sounds interesting 13:15:08 despite the fact that the larger space is uncountable, I think that we can only access countably many positions 13:15:38 due to ITTM rules being countable 13:15:43 right 13:15:54 But it'll be hard to keep track of which positions have been visited and which haven't... 13:16:10 which leads me to suppose that ultimately this is computationally equivalent to ITTMs 13:16:32 I think that's correct, although it's not that obvious ... 13:24:22 Guys! 13:24:26 We were wrong! 13:24:35 This model actually is stronger! 13:24:44 Wait whaaaaat 13:24:52 Let me modify it a bit: 13:24:53 waaat 13:25:00 We have two tapes, scratch and control 13:25:18 Scratch does what it does, control tape controls head in Hilbert space 13:25:33 So now suppose we do the following: 13:25:44 We simulate some machine M on scratch tape 13:26:12 On control tape we write instantaneous description of M at every step 13:26:22 And we move to that position in Hilbert space 13:26:26 And flash that cell 13:26:48 If configuration repeats infinitely many times, this flag will flash infinitely many times 13:26:59 And will ultimately end up being on 13:27:07 So if this configuration happens one more time 13:27:11 We can see that 13:27:15 This way 13:27:21 We can solve halting problem! 13:27:30 Huh. Let me process that a bit. 13:27:41 Because machine doesn't halt iff some it's configuration repeats w times 13:27:53 *its 13:28:17 Scratch is the Z^Z head, right? 13:28:34 No, scratch is another linear tape 13:28:39 I modified model a bit 13:28:47 So we have to linear tapes and Hilbert space 13:28:54 But this can also work on one tape ... 13:29:29 If you're right that it is stronger, then the following extension should also work: 13:29:43 using the Hilbert heads to control vectors in even larger Hilbert spaces 13:30:10 It's hard for me to imagine this 13:30:17 But I guess it might work too 13:30:27 Yeah, I can't really wrap my had around anything of cardinality Beta_2 either :( 13:30:31 *head ... Say cheese! This is a proposal for a highly experimental Hilbert-space ITTM. I call it a "photographic ITTM." PhITTMs have two tapes. One is the control tape, which is an ordinary one-dimensional two-color tape. The other is a photo tape, which is essentially a function \((\mathbb{Z} \mapsto \{0, 1\}) \mapsto \{0, 1\}\). The control tape's head behaves like any other ITTM, but the photo tape's head is a bit different. At each step, the photo head jumps to the position determined by treating the control tape's colors as a vector. The transition function is as follows: :(state, control color, photo color) → (new state, new control color, new photo color, control motion) As usual, at each limit state, all control and photo cells are set to the limit superior of their previous colors. Intuitively, the photographic ITTM can be thought of as an ITTM that can take a "photo" of its tape and store this in an album. At each step, the ITTM can check whether its current tape matches a photo in the album. It also has the options of taking a photo of its current tape or erasing it. At each limit stage, a photo in the album is retained iff it existed for an unbounded amount of time up to that point. Note that state is not included in the photo. I don't know whether inverting this rule has any effect. Why not photographic TMs? If we apply the camera to ordinary TMs, it's not hard to see that the result offers no additional power. A photographic TM can be simulated by an ordinary TM — the album only requires finite memory, and comparing the tape to a photo is a decidable problem. Imagine our surprise when Peng found a convincing (although not yet confirmed) argument showing that PhITTMs can solve the halting problem for ITTMs. We both suspect that they are computationally equivalent to one of the ITTM oracles. Yo dawg Even more experimentally, we can add another photo tape whose head is located according to the colors of the first photo tape, and of course we can continue adding more and more photo tapes. I think they can even be extended into an ordinal hierarchy, where another control tape is used to index the photo tape you want to read from. We don't know whether any additional power is gained by these additions, and the ordinal hierarchy is especially speculative. But it's fun to imagine these things. Category:Blog posts